package com.linran.structure_algorithm.算法.lesson2_排序;

import java.time.Duration;
import java.time.LocalDateTime;
import java.util.Arrays;

/**
 * 快速排序
 */
public class FiveQuickSort {
    public static void main(String[] args) {
        int base = 8000000;
        int[] arr = new int[base];
        for (int i = 0; i < base - 1; i++) {
            arr[i] = (int) (Math.random() * base);
        }
        LocalDateTime start = LocalDateTime.now();
        quickSort(arr, 0, arr.length - 1);
        LocalDateTime end = LocalDateTime.now();
//        System.out.println(Arrays.toString(arr));
        System.out.printf("耗时:%d毫秒%n", Duration.between(start, end).toMillis());
    }

    /**
     * 以右边数为基准，需要先从左边进行查找
     *
     * @param arr
     * @param leftIndex
     * @param rightIndex
     */
    public static void quickSort(int[] arr, int leftIndex, int rightIndex) {
        if (leftIndex >= rightIndex) {
            return;
        }
        int l = leftIndex;
        int r = rightIndex;
        int pivot = arr[rightIndex];
        int temp = 0;
        while (l < r) {
            // 右边数为基准，一定要先从左边开始查询
            // 左边寻找大于基准数的index
            while (arr[l] <= pivot && l < r) {
                l++;
            }
            // 右边寻找小于基准数的index
            while (arr[r] >= pivot && l < r) {
                r--;
            }
            // 交换
            if (l < r) {
                temp = arr[l];
                arr[l] = arr[r];
                arr[r] = temp;
            }
        }
        // 跳出循环时,l==r的，此时交换基准数
        arr[rightIndex] = arr[r];
        arr[r] = pivot;
        // 这里r==l
        quickSort(arr, leftIndex, r - 1);
        quickSort(arr, l + 1, rightIndex);
    }
}